(1) Field of the Invention
The present invention relates to a system and method for automatically and optimally determining routes intervened between circuits (circuit blocks) of Programmable Logic Device (PLD). The present invention, particularly, relates to a system and method for automatically and optimally determining routes between circuits of the PLD in which connections between respective circuit blocks can be made with the shortest possible path with the least number of switching stations between the respective circuit blocks, and, which can effectively be formed using CAD (Computer Aided Design) system in a shorter length of time.
(2) Background of the Art
When Programmable Logic Devices (PLDs) or Logic Cell Arrays (LCAs) are designed for particular uses, it is necessary to determine paths of wiring to interconnect between internal circuit blocks so as to achieve logic circuitry required for a particular use.
For example, in Programmable Logic Devices (PLDs), a plurality of circuit blocks into which logic circuits are incorporated and a plurality of switching stations provided for determining the routes between the respective circuit blocks are regularly arranged in horizontal or vertical array forms.
In addition, a predetermined switching element within each switching station is turned on or off to define the path through the switching station hereinafter, generally referred to as an SS. It will further be noted that generally route will refer to the overall line network sought to be established among the circuit blocks and path will describe one aspect or segment of the total route). Therefore, a signal transmission line between a source pin of one of the circuit blocks and load pin of one of the other circuit blocks is formed to provide a required logic circuitry between each circuit block.
In more detail, each switching station SS, as shown in FIGS. 1 and 2, is provided with a plurality of electrically conductive pins located on four sides thereof, i.e., the N (North) side, S (South) side, W (West) side, and E (East) side, these pins being used to input or output information signals. These conductive pins extended on each side of the switching station SS are connected to those on adjacent switching stations. As shown in FIG. 3, a switching element such as a MOS (Metal Oxide Semiconductor) transistor T is interposed between the associated pins. When the transistor T is turned on, a single path is established between the associated pins so as to enable electrical connection between the pins.
When, e.g., a data of "1" is set in a storage area of SRAM (Static Random Access Memory) connected to a gate of the MOS transistor T, the MOS transistor T is turned on to electrically connect both pins. Between which pins the MOS transistor T is interposed depends on specifications prepared for the switching stations. For example, the plurality of MOS transistors may be installed to respective pins according to such specifications as shown in FIGS. 4 (A) to 4 (M).
As appreciated from FIG. 4 (A), a current path can be established between pins W1 and E1 if the MOS transistor TW1E1 (shown in FIG. 4 (A)) is turned on. Consequently, it is possible to set the connections within respective switching stations according to the user's requirement. Thus, the paths according to the user's requirements can be carried out between a circuit block and an adjacent switching station and between mutually adjoining switching stations.
As described above, a single connection between the circuit blocks to be interconnected can be formed.
A method of determining paths in the PLDs includes, a first, rough determination of the route through a rough selection of SSs, i.e., through which of SSs the wired line between the source pin on one of the circuit blocks and load pin on one of the other circuit blocks is to be passed and a main determination which of the switching transistors within the selected SSs are to be turned on or off.
In order to facilitate the rough determination of path, various types of apparatuses for computer aided design (CAD) have been developed.
The rough determination of paths includes a 1:1 path, i.e., a line wired from a single source pin S to a single load pin L and 1:MULTI (a multiple number of lines), i.e., a single source pin to a plurality of load pins.
A Japanese Patent Application First Publication (unexamined) Showa 63-155740 published on Jun. 28, 1988 exemplifies a wiring method in which the route between a single source pin and a single load pin, or 1:1 wiring, is disclosed.
On the other hand, in the method of 1 (source pin S):MULTI (the multiple number of load pins), particular load pins from among the plurality of load pins are sequentially specified by a user and the required connections are formed such that the required number of load pins are wired to the source to provide the 1:MULTI required by the user.
However, in the above-described method of sequentially specifying a particular load pin from among the plurality of load pins when forming the paths between the respective source pins and load pins, i.e., a 1:MULTI type connection, a total length of each finally determined path becomes long and, thereby, a delay time, i.e., propagation delay of signals of the associated logic circuitry, becomes excessively long so as to reduce an efficiency of the logic circuitry.
Japanese Patent Application First Publications (unexamined) Showa 63-314846 published on Dec. 22, 1988 and Heisei 1-114050 published on May 2, 1989 exemplify a previously proposed method of automatically determining the above-described rough paths utilizing CAD.
In the previously proposed automatic rough route determination methods disclosed in the two above-identified Japanese Patent Application First Publications, to suppress generation of delay time involved in signal propagations between the circuit blocks in the LSI, the shortest paths between the associated blocks to be interconnected are automatically designed without intersections with other wired lines of paths when the circuit blocks to be interconnected are specified by the user.
As shown in FIG. 1, suppose that the circuit blocks to be interconnected B1 and B2 and the user specifies these two blocks B1 and B2 to be interconnected toward the CAD system. The automatic rough path determining method in the system can determine one of the plurality of paths to be taken between B1 and B2, i.e., R1 shown in FIG. 1.
According to the previously proposed apparatuses for automatically determining the rough paths between circuit blocks, a time required to design of the shortest paths can be shortened, as compared with the manual design counterpart, to provide the shortest paths.
However, because of restrictions placed on combinations of paths possible within the switching stations in the PLDs, when a plurality of the combinations of lines between two circuit blocks to be interconnected are present if connection combinations are plurally present and some of paths cannot be determined after the rough path determinations are completed.
That is to say, after the rough path determinations, the main path determinations which select which one of transistors within each SS disposed along the path will be turned on in order to achieve the shortest path.
During the main path determination, to prevent the delay time from increasing within the switching stations present midway along the rough path, it is common practice to form the path as short as possible along a given direction within the respective switching stations.
For example, to effect the shortest route R1 within the switching station SS2, of FIG. 1, the transistors (according to FIG. 4) TW1E1, TW2E2, and TW3E3 are the transistors to be turned on. It will be noted that all the transistors shown in FIG. 4 are present in each switching station SS.
For example, since the route R1 denoted by a solid line on the switching station SS3 and another route R2 denoted by a broken line are to be formed (the other path of R2 serves to connect associated circuit blocks other than B1-B2 of FIG. 1), the transistor TW1N1 is turned on to provide a path between the pins N1-W1 of the switch station SS3. The route from the pin W1 to the pin E1 cannot be simultaneously used by as two routes. If the same occurs in other routes from W2 to E2 or from W3 to E3, as shown in FIGS. 4 (B) and 4 (C), it will not possible to establish the path R1 within SS 3, for example.
Then, if the rough path determinations are continued neglecting the above described conditions, the path determination becomes often impossible if the path determination is carried out after determination of all the rough paths. At this time, it becomes necessary to restart the rough path determinations. This wastefully consumes time as far as design considerations are concerned.
Then, if it is necessary to correct the shortest route R1 by bypassing a problematic switching station SS (SS3, for example, the term problematic switching station will be defined in detail in the DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS), such bypassing is carried out according to no fixed rules, so the total length of the paths become large so that an increase in delay time duration becomes detrimental to the overall design.